package com.leet.code.lcof;

public class Code13 {
    public static void main(String[] args) {
        Code13 code13 = new Code13();
        int c = code13.movingCount(38, 15, 9);
        System.out.println(c);
    }


    int c = 0;
    int m, n, k;
    boolean[][] board;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        board = new boolean[m][n];
        move(0, 0, 0, 0);
        return c;
    }

    public void move(int i, int j, int ic, int jc) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j]) {
            return;
        }
        if (ic + jc > k) {
            return;
        }
        c++;
        board[i][j] = true;
        move(i + 1, j, count10(i + 1, 0), jc);
//        move(i - 1, j);
        move(i, j + 1, ic, count10(j + 1, 0));
//        move(i, j - 1);
    }


    public int count10(int c, int sum) {
        int g = c % 10;
        sum = sum + g;
        int y = c / 10;
        if (y == 0) {
            return sum;
        }
        return count10(y, sum);
    }


}
